"""
1. 走迷宫问题
    从左上角走到右下角，遇到墙走不通
    例如：1 是墙 0是路，从左上角0， 走到右下角0 
    list_ = [
            [1,1,1,1,1,1,1,1,1],
            [1,0,0,1,1,1,1,1,1],
            [1,0,0,1,0,1,1,1,1],
            [1,1,0,0,0,0,1,1,1],
            [1,1,1,0,1,0,0,0,1],
            [1,1,0,0,0,0,1,0,1],
            [1,1,1,1,0,0,1,0,1],
            [1,1,1,0,0,0,0,0,1],
            [1,1,1,1,1,1,1,1,1],
        ]

队列解法： 广度优先， 找最优解
# 讲解
    queue = [(1,1)]
    
    (1,1) 出栈引入
    queue = [(1,2), (2,1)]
    (1,2) 出栈引入
    queue = [(2,1), (2,2)]
    (2,1) 出栈无引入
    queue = [(2,2)]
    (2,2) 出栈引入
    queue = [(3,2)]
    (3,2) 出栈引入
    queue = [(3,3)]
    (3,3) 出栈引入
    queue = [(4,3), (4,4)]
    ...

思路：  
    从一个节点开始，寻找所有接下来能个继续走的点，继续不断寻找，直到找到出口。
    
    * 使用队列存储当前正在考虑的节点。
        # 在一个点出队的时候， 将这个点可能引入的点存到队列中。
    * 另外开辟一个存储空间，来存储每一个点，是由哪个点引入的，
      在展示路径的时候反向查找展示。
"""

import time

def find_min_route(x1, y1, x2,y2, list_):
    queue = []
    queue.append((x1, y1))
    func = [
        lambda x,y: (x-1, y), # 向上
        lambda x, y: (x+1, y), # 向下
        lambda x, y: (x, y-1), # 向左
        lambda x, y: (x, y+1) # 向右 
    ]
    # 记录每个节点的父节点
    dict_ = {(x1, y1): -1}
    # 也可以在队列中存放一个（x,y, 父节点下标）。 path = [] 存放父节点
    list_[1][1] = 2
    # 将起始位置标记为已走
    while len(queue) > 0:
        now_point = queue.pop(0)
        if now_point[0] == x2 and now_point[1] == y2:
            # 遍历输出结果
            tmp = (x2, y2)
            # 存放正序结果
            real_path = [tmp]
            while dict_[tmp] != -1:
                tmp = dict_[tmp]
                real_path.insert(0, tmp)
            print(real_path)
            return True
        
        # 四个方向
        for fun in func:
            next_point = fun(now_point[0], now_point[1])
            # 把所有满足条件的都记下来
            if list_[next_point[0]][next_point[1]] == 0:
                queue.append(next_point)
                dict_[next_point] = now_point
                # 将已经走过的做标记， 防止重复走，卡bug
                list_[next_point[0]][next_point[1]] = 2
    return False


list_ = [
            [1,1,1,1,1,1,1,1,1],
            [1,0,0,1,1,1,1,1,1],
            [1,0,0,1,0,1,1,1,1],
            [1,1,0,0,0,0,1,1,1],
            [1,1,1,0,1,0,0,0,1],
            [1,1,0,0,0,0,1,0,1],
            [1,1,1,1,0,0,1,0,1],
            [1,1,1,0,0,0,0,0,1],
            [1,1,1,1,1,1,1,1,1],
        ]
result = find_min_route(1,1, 7,7, list_)
print(result)